/*
 * @lc app=leetcode.cn id=44 lang=golang
 *
 * [44] 通配符匹配
 */

// @lc code=start

func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	res := make([]bool, n+1)
	isStarTrue := true // 判断是否为第一个 *
	// 注意初始化时，不是最前方的*号无法匹配空字符串
	for i, _ := range res {
		if i == 0 {
			res[i] = true
			continue
		}
		if p[i-1] != '*' {
			res[i] = false
			isStarTrue = false
		} else {
			if isStarTrue {
				res[i] = true
			} else {
				res[i] = false
			}
		}
	}
	for i := 0; i < m; i++ {
		tmp := make([]bool, n+1)
		tmp[0] = false
		for j := 0; j < n; j++ {
			if s[i] == p[j] || p[j] == '?' {
				tmp[j+1] = res[j]
			} else if p[j] == '*' {
				tmp[j+1] = tmp[j] || res[j+1]
			} else {
				tmp[j+1] = false
			}
		}
		res = tmp
	}
	return res[n]
}

// @lc code=end
